package com.leetcode.no62;

import java.util.*;

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] dp = new int[n][m];

        // dp数组代表什么？
        // dp[n][m]代表机器人在(n,m)上，有多少种走法

        for (int i = 0; i <= n - 1; i++) {
            // 第一列
            dp[i][0] = 1;
        }

        for (int j = 0; j <= m - 1; j++) {
            // 第一行
            dp[0][j] = 1;
        }

        for(int i=1; i <= n-1; i++){
            for(int j=1; j<=m-1; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[n - 1][m - 1];
    }

    public int uniquePaths01(int m, int n) {

        long ans = 1;
        int rows = Math.min(m - 1, n - 1);
        for (int i = 0; i <= rows-1; i++) {
            ans *= m + n - 2 - i;
            ans /= i + 1;
        }
        return (int) ans;
    }
    public int uniquePaths02(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }

}
